package com.zdp.leetcodeMiddle;


import com.zdp.util.TreeNode;

/*
* 题目描述：
* 根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7
* */
public class 从中序和后序遍历序列构造二叉树_106 {

    /*
    * 解题思路：参考重建二叉树_offer07
    * */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return f(inorder,postorder,0,inorder.length-1,inorder.length-1);
    }

    public TreeNode f(int[] inorder,int[] postorder,int left,int right,int index){
        // 确认一个根节点
        if(left>right){
            return null;
        }
        if(index<0){
            return null;
        }
        // 找到左右子树区间
        int mid = 0;
        for(int i=left; i<=right;i++){
            if(inorder[i] == postorder[index]){
                mid = i;
            }
        }
        TreeNode t = new TreeNode();
        t.val = postorder[index];
        t.right = f(inorder,postorder,mid+1,right,index-1);
        t.left = f(inorder,postorder,left,mid-1,index-1-right+mid);
        return t;
    }
}
